package linked_list;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        Node n1 = new Node(1, "a");
        Node n2 = new Node(2, "b");
        Node n3 = new Node(3, "c");
        Node n4 = new Node(4, "d");
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        // singleLinkedList.add(n1);
        // singleLinkedList.add(n2);
        // singleLinkedList.add(n3);
        // singleLinkedList.add(n4);
        singleLinkedList.addByOrder(n1);
        singleLinkedList.addByOrder(n1);
        singleLinkedList.addByOrder(n4);
        singleLinkedList.addByOrder(n2);
        singleLinkedList.addByOrder(n3);
        singleLinkedList.show();
        singleLinkedList.updateNode(3, "cc");
        singleLinkedList.updateNode(5, "ee");
        singleLinkedList.show();
        singleLinkedList.deleteNode(3);
        singleLinkedList.deleteNode(5);
        singleLinkedList.show();
    }
}

// 链表定义
class SingleLinkedList {
    // 创建头节点
    private Node head = new Node(0, "");

    // 在链表末尾添加元素
    public void add(Node node) {
        // 找到链表的最后
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        // 加入新节点
        temp.next = node;
    }

    // 按编号顺序插入节点
    public void addByOrder(Node node) {
        // 找到插入位置的前一个节点
        Node temp = head;
        while (true) {
            // 若遍历完了整个链表，说明该节点应插入最后
            if (temp.next == null) {
                break;
            }
            // 若temp.next的no大于待插入节点的no，说明插入位置在temp和temp.next之间
            if (temp.next.no > node.no) {
                break;
            } else if (temp.next.no == node.no) {
                System.out.println("已有同编号的节点");
                return;
            }
            temp = temp.next;
        }
        // 添加节点
        node.next = temp.next;
        temp.next = node;

    }

    // 更新节点信息
    public void updateNode(int no, String name) {
        Node temp = head;
        while (temp.next != null) {
            if (temp.next.no == no) {
                temp.next.name = name;
                return;
            }
            temp = temp.next;
        }
        System.out.println("未找到该节点");
    }

    // 删除节点
    public void deleteNode(int no) {
        Node temp = head;
        while (temp.next != null) {
            if (temp.next.no == no) {
                temp.next = temp.next.next;
                return;
            }
            temp = temp.next;
        }
        System.out.println("未找到该节点");
    }

    // 输出链表
    public void show() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        Node temp = head.next;
        while (temp != null) {
            System.out.println(temp.toString());
            temp = temp.next;
        }
    }

}

// 节点定义
class Node {

    // data域
    public int no;
    public String name;

    // 指针域
    public Node next;

    public Node(int no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node [no=" + no + ", name=" + name + "]";
    }
}